package leetcode.D400.T322;

import java.util.Arrays;

class Solution {
    /*// 一刷
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i=1; i<=amount; ++i) {
            int minNum = Integer.MAX_VALUE;
            for(int j=0; j<coins.length; ++j) {
                if(i - coins[j] < 0 || dp[i-coins[j]] < 0) continue;
                minNum = Integer.min(minNum, dp[i-coins[j]]);
            }
            dp[i] = minNum < Integer.MAX_VALUE ? minNum + 1 : -1;
        }
        return dp[amount];
    }*/

    /*// 二刷
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=0; i<coins.length; ++i) {
            for(int j=0; j<=amount; ++j) {
                if(j - coins[i] < 0 || dp[j-coins[i]] == Integer.MAX_VALUE) {
                    continue;
                }
                dp[j] = Integer.min(dp[j], dp[j-coins[i]] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }*/

    // 三刷
    /*public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        Arrays.sort(coins);
        for(int i=1; i<=amount; ++i) {
            for(int j=0; j<coins.length; ++j) {
                if (coins[j] > i) {
                    break;
                }
                if (dp[i-coins[j]] < 0) {
                    continue;
                }
                dp[i] = Math.min(dp[i], dp[i-coins[j]]+1);
            }
            if(dp[i] == Integer.MAX_VALUE) {
                dp[i] = -1;
            }
        }
        return dp[amount];
    }*/

    // 四刷
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.sort(coins);
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i=1; i<=amount; ++i) {
            for(int j=0; j<coins.length; ++j) {
                int k = i - coins[j];
                if (k < 0)
                    break;
                if (dp[k] == Integer.MAX_VALUE)
                    continue;
                dp[i] = Math.min(dp[i], dp[k]+1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}